class Solution {
    public:
        void getnext(string& needle,vector<int>& next){
            int n = needle.size();
            next[0] = 0;
            int j = 0; //j表示当前状况下前后相等缀串的最长长度
            int i = 1; //从1开始
            while(i < n){
                if(needle[j] == needle[i]){
                    next[i++] = ++j;  //这种情况最长长度+1
                }else if( j > 0 && needle[j] != needle[i]){
                    j = next[j-1];   //这种情况需要在前缀中找前缀 和后缀的后缀相等，再继续想后比较
                }else{
                    //j == 0;      //当j回到0是就直接next[i] 为0
                    next[i++] = 0;
                }
            }
        }
        int strStr(string haystack, string needle) {
            int m = haystack.size(),n=needle.size();
            vector<int> next(n,0);
            getnext(needle,next);
            int j = 0 ;//表示neddle的当前下标位置
            int i = 0 ;//表示haystack的下标位置
            while(i < m){
                if(haystack[i] ==needle[j]){
                    ++j;                 
                    ++i;               //暂时相同
                }else if(j > 0 && haystack[i] != needle[j]){
                    j = next[j-1];   //因为之前的前后缀相等，直接回到前缀后
                }else{
                    i++; //j到0都没成功
                }
                if(j == n){
                    return i-n; 
                }
            }
            return -1;
        }
    };